SQL Server 2008 R2 : Space Allocation Structures

When a table or index needs more space in a database, SQL Server needs a way to determine where space is available in the database to be allocated. If the table or index is still fewer than eight pages in size, SQL Server must find a mixed extent with one or more pages available that can be allocated. If the table or index is eight pages or larger in size, SQL Server must find a free uniform extent that can be allocated to the table or index.

Extents

If SQL Server allocated space one page at a time as pages were needed for a table (or an index), SQL Server would be spending a good portion of its time just allocating pages, and the data would likely be scattered noncontiguously throughout the database. Scanning such a table would not be very efficient. For these reasons, pages for each object are grouped together and allocated in extents; an extent consists of eight logically contiguous pages.

When a table or index is created, it is initially allocated a page on a mixed extent. If no mixed extents are available in the database, a new mixed extent is allocated. A mixed extent can be shared by up to eight objects (each page in the extent can be assigned to a different table or index).

As the table grows to at least eight pages in size, all future allocations to the table are done as uniform extents.

Figure 1 shows the use of mixed and uniform extents.

Figure 1. Mixed and uniform extents.

If SQL Server had to search throughout an entire database file to find free extents, it wouldn’t be efficient. Instead, SQL Server uses two special types of pages to record which extents have been allocated to tables or indexes and whether it is a mixed or uniform extent:

• Global allocation map pages (GAMs)

• Shared global allocation map pages (SGAMs)

Global and Shared Global Allocation Map Pages

The allocation map pages track whether extents have been allocated to objects and indexes and whether the allocation is for mixed extents or uniform extents. As mentioned in the preceding section, there are two types of GAMs:

• Global allocation map (GAM)— The GAM keeps track of all allocated extents in a database, regardless of what it’s allocated to. The structure of the GAM is straightforward: each bit in the page outside the page header represents one extent in the file, where 1 means that the extent is not allocated, and 0 means that the extent is allocated. Nearly 8,000 bytes (64,000 bits) are available in a GAM page after the header and other overhead bytes are taken into account. Therefore, a single GAM covers approximately 64,000 extents, or 4GB (64,000 * 64KB) of data.

• Shared global allocation map (SGAM)— The SGAM keeps track of mixed extents that have free space available. An SGAM has a structure similar to a GAM, with each bit representing an extent. A value of 1 means that the extent is a mixed extent and there is free space (at least one unused page) available on the extent. A value of 0 means that the extent is not currently allocated, that the extent is a uniform extent, or that the extent is a mixed extent with no free pages.

Table 1 summarizes the meaning of the bit in GAMs and SGAMs.

When SQL Server needs to allocate a uniform extent, it simply searches the GAM for a bit with a value of 1 and sets it to 0 to indicate it has been allocated. To find a mixed extent with free pages, it searches the SGAM for a bit set to 1. When all pages in a mixed extent are used, its corresponding bit is set to 0. When a mixed extent needs to be allocated, SQL Server searches the GAM for an extent whose bit set to 1 and sets the bit to 0, and the corresponding SGAM bit is set to 1. There is some more processing involved as well, such as spreading the data evenly across database files, but the allocation algorithms are still relatively simple.

SQL Server is able to easily locate GAM pages in a database because the first GAM page is located at the third page in the file (page number 2). There is another GAM every 511,230 pages after the first GAM. The fourth page (page number 3) in each database file is the SGAM page, and there is another SGAM each 511,230 pages after the first SGAM.

Page Free Space Pages

A page free space (PFS) page records whether each page is allocated and the amount of free space available on the page. Each PFS covers 8,088 contiguous pages in the file. For each of the 8,088 pages, the PFS has a 1-byte record that contains a bitmap for each page indicating whether the page is empty, 1 to 50% full, 51 to 80% full, 81 to 95% full, or more than 95% full. The first PFS page in a file is located at page number 1, the second PFS page is located at page 8088, and each additional PFS page is located every 8,088 pages after that. SQL Server uses PFS pages to find free pages on extents and to find pages with space available on extents when a new row needs to be added to a table or index.

Figure 2 shows the layout of GAM, SGAM, and PFS pages in a database file. Note that every file has a single file header located at page 0.

Figure 2. The layout of GAM, SGAM, and PFS pages in a database file.

Index Allocation Map Pages

Index allocation map (IAM) pages keep track of the extents used by a heap or index. Each heap table and index has at least one IAM page for each file where it has extents. An IAM cannot reference pages in other database files; if the heap or index spreads to a new database file, a new IAM for the heap or index is created in that file. IAM pages are allocated as needed and are spread randomly throughout the database files.

An IAM page contains a small header that has the address of the first extent in the range of pages being mapped by the IAM. It also contains eight page pointers that keep track of index or heap pages that are in mixed extents. These pointers might or might not contain any information, depending on whether any data has been deleted from the tables and the page(s) released. Remember, an index or heap will have no more than eight pages in mixed extents (after eight pages, it begins using uniform extents), so only the first IAM page stores this information. The remainder of the IAM page is for the allocation bitmap. The IAM bitmap works similarly to the GAM, indicating which extents over the range of extents covered by the IAM are used by the heap or index the IAM belongs to. If a bit is on, the corresponding extent is allocated to the table.

Each IAM covers a possible range of 63,903 extents (511,224 pages), covering a 4GB section of a file. Each bit represents an extent within that range, whether or not the extent is allocated to the object that the IAM belongs to. If the bit is set to 1, the relative extent in the range is allocated to the index or heap. If the bit is set to 0, the extent is either not allocated or might be allocated to another heap or index.

For example, assume that an IAM page resides at page 649 in the file. If the bit pattern in the first byte of the IAM is 1010 0100, the first, third, and sixth extents within the range of the IAM are allocated to the heap or index. The second, fourth, fifth, seventh, and eighth extents are not.

Differential Changed Map Pages

The seventh page (page number 6), and every 511,232nd page thereafter, in the database file is the differential changed map (DCM) page. This page keeps track of which extents in a file have been modified since the last full database backup. When an extent has been modified, its corresponding bit in the DCM is turned on. This information is used when a differential backup is performed on the database. A differential backup copies only the extents changed since the last full backup was made. Using the DCM, SQL Server can quickly tell which extents need to be backed up by examining the bits on the DCM pages for each data file in the database. When a full backup is performed for the database, all the bits are set back to 0.

Bulk Changed Map Pages

The eighth page (page number 7), and every 511,232nd page thereafter, in the database file is the bulk changed map (BCM). When you perform a minimally or bulk-logged operation in SQL Server 2008 in BULK_LOGGED recovery mode, SQL Server logs only the fact that the operation occurred and doesn’t log the actual data changes. The operation is still fully recoverable because SQL Server keeps track of what extents were actually modified by the bulk operation in the BCM page. Similar to the DCM page, each bit on a BCM page represents an extent within its range, and if the bit is set to 1, that indicates that the corresponding extent has been changed by a minimally logged bulk operation since the last full database backup. All the bits on the BCM page are reset to 0 whenever a full database backup or log backup occurs.

When you initiate a log backup for a database using the BULK_LOGGED recovery model, SQL Server scans the BCM pages and backs up all the modified extents along with the contents of the transaction log itself. You should be aware that the log file itself might be small, but the backup of the log can be many times larger if a large bulk operation has been performed since the last log backup.